/*
 * @lc app=leetcode.cn id=145 lang=golang
 *
 * [145] 二叉树的后序遍历
 */

// 2. 循环
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (ans []int) {
	stack := []*TreeNode{}
	var pre *TreeNode
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		if stack[len(stack)-1].Right != nil && stack[len(stack)-1].Right != pre {
			root = stack[len(stack)-1].Right
		} else {
			ans = append(ans, stack[len(stack)-1].Val)
			pre = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			root = nil
		}
	}

	return
}

// @lc code=end

// 1. 递归
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (ans []int) {
	var postorder func(node *TreeNode)
	postorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		postorder(node.Left)
		postorder(node.Right)
		ans = append(ans, node.Val)
	}

	postorder(root)
	return
}

// @lc code=end

